/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhong
 *
 */
public class PartitionLabels {
	public List<Integer> partitionLabelsWindow(String S) {
		List<Integer> res = new ArrayList<>();

		int[] freq = new int[26];
		boolean newly[] = new boolean[26];
		for (int i = 0; i < S.length(); i++) {
			freq[S.charAt(i) - 'a']++;
		}
		int todo = 0;
		int last = -1;
		for (int i = 0; i < S.length(); i++) {
			int index = S.charAt(i) - 'a';
			// 如果新出现
			if (!newly[index]) {
				newly[index] = true;
				todo++;
			}
			freq[index]--;
			if (freq[index] == 0) {
				todo--;
				if (todo == 0) {
					res.add(i - last);
					last = i;
				}
			}
		}
		return res;
	}

	public List<Integer> partitionLabels(String S) {
		List<Integer> res = new ArrayList<>();
		int[][] char2pos = new int[26][2];
		boolean[] exist = new boolean[26];
		for (int j = 0; j < S.length(); j++) {
			int ch = S.charAt(j) - 'a';
			if (!exist[ch]) {
				exist[ch] = true;
				char2pos[ch][0] = j + 1;
				char2pos[ch][1] = j + 1;
			} else {
				char2pos[ch][1] = j + 1;
			}
		}
		Arrays.sort(char2pos, (a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
		int j = 0;
		while (char2pos[j][0] == 0) {// 没开始
			j++;
		}
		int start = char2pos[j][0], end = char2pos[j][1];
		j++;
		for (; j < exist.length; j++) {
			if (end > char2pos[j][0]) {// 合并
				end = Math.max(end, char2pos[j][1]);
			} else {
				res.add(end - start + 1);
				start = char2pos[j][0];
				end = char2pos[j][1];
			}
		}
		res.add(end - start + 1);
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "caedbdedda";// jybmxfgseq
		// ababcbacadefegdehijhklij
		// "caedbdedda"
		System.out.println(new PartitionLabels().partitionLabelsWindow(S));
		System.out.println(new PartitionLabels().partitionLabels(S));
	}

}
